// https://leetcode.cn/problems/interleaving-string/

// 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 暴力会超时
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.size();
        int len2 = s2.size();
        int len3 = s3.size();
        if (len1 + len2 != len3) return false;
        bool flag = false;
        auto dfs = [&](auto &&me) {
            if (len3 == 0 && len2 == 0 && len1 == 0) {
                flag = true;
                return;
            }
            if (len3 > 0 && len2 > 0 && s3[len3 - 1] == s2[len2 - 1]) {
                len3--;
                len2--;
                me(me);
                len3++;
                len2++;
            }

            if (len3 > 0 && len1 > 0 && s3[len3 - 1] == s1[len1 - 1]) {
                len3--;
                len1--;
                me(me);
                len3++;
                len1++;
            }
        };

        dfs(dfs);
        return flag;
    }

    // 动态规划
    /*
     * i代表s1的第i个字符
     * j代表s2的第j个字符
     * s3的第 i+j 序列的字母等于 s3[i+j-1] + s2[j] 或者 s3[i+j-1] + s1[i]
     * */
    bool isInterleave1(string s1, string s2, string s3) {
        int len1 = s1.size();
        int len2 = s2.size();
        int len3 = s3.size();
        if (len1 + len2 != len3) return false;
        int dp[len1 + 1][len2 + 1];
        dp[0][0] = 1;
        for (int i = 1; i < len1; i++) {
            dp[i][0] = dp[i - 1][0] && s3[i - 1] == s1[i - 1];
        }
        for (int j = 1; j < len2; j++) {
            dp[0][j] = dp[0][j - 1] && s3[j - 1] == s2[j - 1];
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (dp[i - 1][j] == 1 && s1[i - 1] == s3[i + j - 1] ||
                    dp[i][j - 1] == 1 && s2[j - 1] == s3[i + j - 1]) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return dp[len1][len2];
    }
};

int main() {
    Solution so;
    string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
    /**
     * a a d b b c b c a c
     * a a   b   c   c
     *     d   b   b   a c
     *
     * dp[i+j] = dp[i+j-1] + s1[i] | dp[i+j-1] + s2[j]
     */
    bool res = so.isInterleave1(s1, s2, s3);
    if (res) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
    return 0;
}